package com.cat.binaryAnswer;

/**
*   @description https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
*   @author 曲大人的喵
*   @create 2025/8/11 09:26
*   @since JDK17
*/

public class Solution07 {
    boolean check(int[] weights, int days, int target) {
        int cnt = 1, cur = target, n = weights.length;
        for (int i = 0; i < n; i++) {   //
            if (cur < weights[i]) {
                cur = target - weights[i];
                cnt++;
            } else {
                cur -= weights[i];
            }
        }
        return cnt <= days;
    }

    public int shipWithinDays(int[] weights, int days) {
        if (weights.length == 1) {
            return weights[0];
        }
        int n = weights.length, max = weights[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, weights[i]);
        }
        int l = max - 1, r = max * n / days + 1, mid;
        while (l + 1 < r) {
            mid = l + (r - l) / 2;
            if (check(weights, days, mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return r;
    }
}
